package com.demo.java.OD401_450.OD409;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【计算三叉搜索树的高度(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146253419
 */
public class OdMain {

    static class Node {
        int val;
        Node left, mid, right;

        Node(int val) {
            this.val = val;
            this.left = null;
            this.mid = null;
            this.right = null;
        }
    }

    // 记录当前的最大深度
    static int ans = 1;

    // 深度优先搜索插入节点
    static void dfs(Node curNode, int val, int curDepth) {
        // 如果值比当前节点值小500，则插入左子树
        if (val - curNode.val < -500) {
            if (curNode.left == null) {
                curNode.left = new Node(val);  // 插入新节点
                ans = Math.max(ans, curDepth + 1);  // 更新最大深度
                return;
            }
            dfs(curNode.left, val, curDepth + 1);  // 递归插入
        }
        // 如果值比当前节点值大500，则插入右子树
        else if (val - curNode.val > 500) {
            if (curNode.right == null) {
                curNode.right = new Node(val);  // 插入新节点
                ans = Math.max(ans, curDepth + 1);  // 更新最大深度
                return;
            }
            dfs(curNode.right, val, curDepth + 1);  // 递归插入
        }
        // 如果值在当前节点的区间内，则插入中子树
        else {
            if (curNode.mid == null) {
                curNode.mid = new Node(val);  // 插入新节点
                ans = Math.max(ans, curDepth + 1);  // 更新最大深度
                return;
            }
            dfs(curNode.mid, val, curDepth + 1);  // 递归插入
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的节点数量
        int n = scanner.nextInt();
        int[] vals = new int[n];

        // 读取每个节点的值
        for (int i = 0; i < n; i++) {
            vals[i] = scanner.nextInt();
        }

        // 初始化根节点
        Node root = new Node(vals[0]);

        // 对每个节点值进行深度优先搜索插入
        for (int i = 1; i < n; i++) {
            dfs(root, vals[i], 1);  // 从根节点开始插入
        }

        // 输出最大深度
        System.out.println(ans);
    }
}
